package BinaryTree;//给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
//
// 假定 BST 有如下定义： 
//
// 
// 结点左子树中所含结点的值小于等于当前结点的值 
// 结点右子树中所含结点的值大于等于当前结点的值 
// 左子树和右子树都是二叉搜索树 
// 
//
// 例如： 
//给定 BST [1,null,2,2], 
//
//    1
//    \
//     2
//    /
//   2
// 
//
// 返回[2]. 
//
// 提示：如果众数超过1个，不需考虑输出顺序 
//
// 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内） 
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 👍 375 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class findMode {

    List<Integer> res = new ArrayList<>();  //结果集
    TreeNode pre = null;
    int maxCount = 0;  //频率最大计数
    int count = 0;  //当前元素频率
    public int[] findMode1(TreeNode root) {
        /**
         * 二叉搜索数特性 中序遍历下的是递增的
         * 所以可以转换成递增数组求众数，也可以直接中序遍历下求众数
         * 候选人算法，count遇到一次curr加1，不是curr就减一，如果为0,更新curr和count
         * */

        if (root == null) {
            return new int[0];
        }
        TreeNode curr = root;
        Stack<TreeNode> stack = new Stack<>();
        while(curr!=null || !stack.isEmpty()){
            if(curr!=null){
                stack.push(curr);
                curr =curr.left;   //左
            }else{
                curr = stack.pop();  //中
                /**
                 * 计数，如果遍历前一个节点和当前节点值相同，计数加1，
                 * 若不同或这是第一个节点，计数置1
                 * */
                if(pre==null || pre.val != curr.val){
                    count = 1;
                }else{
                    count++;
                }
                //更新最大频率 和添加众数
                if(count>maxCount){
                    maxCount = count;
                    res.clear();  //当前节点的频率大于最大节点时，清空已经添加的
                    res.add(curr.val);
                }else if(count==maxCount){
                    res.add(curr.val);
                }
                pre = curr;
                curr = curr.right;
            }
        }

        int[] r = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            r[i] = res.get(i);
        }
        return r;
    }

    public int[] findMode(TreeNode root) {
        /**
         * 递归
         * */
        if (root == null) {
            return new int[0];
        }
        helper(root);
        int[] r = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            r[i] = res.get(i);
        }
        return r;

    }

    private void helper(TreeNode root){
        /**
         * 这里是遍历每一个元素，不需要返回值*/
        if(root==null){
            return;
        }
        helper(root.left);
        if(pre==null || root.val != pre.val){
            count = 1;
        }else{
            count++;
        }
        if(count>maxCount){
            maxCount = count;
            res.clear();;
            res.add(root.val);
        }else if(count==maxCount){
            res.add(root.val);
        }
        pre = root;
        helper(root.right);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
